package main.leetcode.clockin.July;

/**
 * 718. 最长重复子数组
 *
 * <p>给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
 *
 * <p>示例：输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。
 *
 * <p>提示：1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100
 */
public class day1 {
    public static void main(String[] args) {
        System.out.println(
                new day1().findLength(new int[] {1, 2, 3, 2, 1}, new int[] {3, 2, 1, 4, 7}));
    }

    // 暴力，tle
    //    public int findLength(int[] A, int[] B) {
    //        int m = A.length;
    //        int n = B.length;
    //        int res = 0;
    //        for (int i = 0; i < n; ++i) {
    //            for (int j = 0; j < n; ++j) {
    //                int k = 0;
    //                while (i + k < m && j + k < n && A[i + k] == B[j + k]) {
    //                    ++k;
    //                }
    //                res = Math.max(res, k);
    //            }
    //        }
    //        return res;
    //    }

    protected int findLength(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int[][] dp = new int[m + 1][n + 1];
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                dp[i + 1][j + 1] = A[i] == B[j] ? dp[i][j] + 1 : 0;
                res = Math.max(res, dp[i + 1][j + 1]);
            }
        }
        return res;
    }

    static class Print implements Runnable {
        @Override
        public void run() {}
    }
}
